1. Field of the Invention
The present invention relates to embedded testing of components in a system that can be modeled through extended finite state machines.
2. Description of the Prior Art
With the advanced computer technology and the increasing demand from the users for sophisticated services, communication protocol systems are becoming more complex, yet less reliable. Conformance testing, which ensures correct protocol implementations, has become indispensable for the development of reliable communication systems. Traditional testing methods tend to test these systems as a whole or alternately test their components in isolation. Testing these systems as a whole becomes difficult due to the formidable size of the systems. Furthermore, testing system components in isolation may not be always feasible due to the interactions among the individual system components. Typically, the tester does not have a direct access to the component under test; access is obtained through other components of the system. As a result, Embedded testing or testing in context has become one of the main focuses of conformance testing research in recent years. The goal of embedded testing is to test whether an implementation of a system component conforms to its specification in the context of other components. If control and observation are applied through one or more implementations that are above the protocol to be tested, the testing methods are called xe2x80x9cembedded.xe2x80x9d
Different approaches for embedded testing are currently in use. These approaches are based on (1) fault models, (2) on reducing the problem to testing of components in isolation, (3) on test suite minimization, (4) on fault coverage, and (5) on the test of systems with semi-controllable and uncontrollable interfaces. Most of these approaches resort to reachability graphs to model the joint behaviors of all the system components. Unfortunately, the implementation of these approaches is plagued by state space explosion, as well as random walk errors.
The problem of random walk remains prevalent under current systems. For example, for a given system component, there is generally a need to test all the transitions or certain boundary values of system variables. Conventionally, a reachability graph is constructed, which is the Cartesian product of all the system components involved. Next, a test is derived that covers all the pre-specified parts of the component under test. Unfortunately, this exhaustive search technique is often impractical; it is impossible to construct a reachability graph for practical systems due to the state space explosion. To avoid this problem random walks have been proposed. At any moment, it is only necessary to keep track of the current states of all the components and determine the next step of test at random. This approach avoids the state space explosion but it may repeatedly test covered parts and take a long time to move on to the untested parts.
Furthermore, a random walk may become xe2x80x9ctrappedxe2x80x9d at a certain part of the component under test or in a small neighborhood. Also, random walks have a low probability of crossing a xe2x80x9cnarrow bridgexe2x80x9d to test the parts beyond the bridge, and may also miss unmarked transitions, even if they are nearby (more than one step from the current node). Finally, the great reliance on reachability graphs restricts space requirements in testing, and is dependent on the system under consideration.
The present invention, referred to as xe2x80x9cHit-or-Jumpxe2x80x9d provides a more efficient and accurate modeling environment through the use of communicating extended unit state machines (CEFSM). Specifically, a new method and system is disclosed for embedded testing of CEFSM""s. The CEFSM model can also be easily adapted to other mathematical models such as Transition Systems, Labeled Transition Systems, and Petri Nets.
Specifically, the present invention tests pre-specified parts of a system component that is embedded in a complex communication system. The pre-specified parts are determined by practical needs or by system certification requirements. Thus, all the transitions or certain boundary values of system variables may be tested for a given system component. Under the xe2x80x9cHit-or-Jumpxe2x80x9d method and system, a local search is conducted from the current state in a neighborhood of the reachability graph. If an untested part is found (a xe2x80x9cHitxe2x80x9d), that part is tested, and the process continues from that point. Otherwise, a subsequent random move is made to the frontier of the neighborhood searched (xe2x80x9cJumpxe2x80x9d), where the process then continues. This procedure avoids the construction of a complete system reachability graph. Furthermore, the space required is determined by the user, and it is independent of the systems under consideration. While a random walk may get xe2x80x9ctrappedxe2x80x9d at certain part of the component under test, the disclosed method and system is designed to xe2x80x9cjumpxe2x80x9d out of the trap and pursue the exploration further.
In a preferred embodiment, the Hit-or-Jump method is applied to the embedded testing of services on a telephone network. The examples given below typify the invention utilized in a system using the signaling data link (SDL) language. The telephone services associated with the invention appear in an Intelligent Network (IN) architecture with Basic Call Services (BCSs). In addition to BCS, five other services are included: Originating Call Screening (OCS), Terminating Call Screening (TCS), Call Forward Unconditional (CFU), Call Forward on Busy Line (CBL) and Automatic Call Back (ACB).